import java.util.ArrayList;

/**
 * Dijkstra's algorithm that solves the single-source shortest 
 * path problem for a graph with nonnegative edge path costs.
 * The edge path costs change respect to the number of node that 
 * compose the path. 
 * @author marcotezzele
 *
 */
public class Dijkstra {

	private double[] distance; 
	private int[] previous;
	private ArrayList<Integer> reversePath;
	private ArrayList<Integer> path;
	private boolean[] isVisit;
	private int carCapacity; 
	private boolean foundPath;
	
	/**
	 * Create all the vectors and in particular
	 * initialize the distance vector with the maximum integer value
	 * and the isVisit vector with false.
	 * @param nodesNumber Number of nodes 
	 */
	public Dijkstra(int nodesNumber, int carCapacity) {
		this.distance = new double[nodesNumber];
		this.previous = new int[nodesNumber];
		this.reversePath = new ArrayList<Integer>();
		this.path = new ArrayList<Integer>();
		this.isVisit = new boolean[nodesNumber];
		this.carCapacity = carCapacity;
		
		for (int i = 0; i < nodesNumber; ++i) {
			this.distance[i] = Integer.MAX_VALUE;
			this.isVisit[i] = false;
		}
	}
	
	/**
	 * Initialize the distance vector and the previous one for the 
	 * source node 
	 * @param source source node
	 */
	public void init(int source) {
		this.distance[source] = 0;
		this.previous[source] = -1;
	}
	
	/**
	 * The core of Dijkstra's algorithm
	 * @param target Target node
	 * @param map Map that contains the matrix of distances
	 * @param nodesNumber Number of nodes
	 */
	public void findPath(int target, Map map, int nodesNumber) 
			throws IllegalArgumentException {
		
		if (target >= nodesNumber) {
			throw new IllegalArgumentException("Target node (" + target + 
					") exceeds number of nodes (" + nodesNumber + ") cause " +
					"the start index is 0");
		}
		/**
		 * TODO controllare che l'inizializzazione di currentNode in 
		 * questo modo non sia fonte di errori.
		 */
		int currentNode = -1;
		double minDistance;
		
		/**
		 * TODO sostituire il ciclo for con un while do nel caso sia 
		 * computazionalmente piu' economico.
		 */
		for ( ; ; ) {
			minDistance = Integer.MAX_VALUE;
			for (int i = 0; i < nodesNumber; i++) {
				if (!this.isVisit[i] && this.distance[i] < minDistance) {
					currentNode = i;
					minDistance = this.distance[currentNode];					
				}
			}
			this.isVisit[currentNode] = true;
			
			if (currentNode == target) {
				foundPath = true;
				break;
			}
			if (minDistance == Integer.MAX_VALUE) {
				foundPath = false;
				break;
			}
			
			for (int i = 0; i < nodesNumber; i++) {
				if ( map.getDistance(currentNode, i) > 0 && this.distance[i] > 
						this.distance[currentNode] + 
						map.getDistance(currentNode, i) / 
						this.passengerNumber(currentNode) ) {
					this.distance[i] = this.distance[currentNode] + 
							map.getDistance(currentNode, i) / 
							this.passengerNumber(currentNode);
					this.previous[i] = currentNode;
				}
			}
			
		}
	}
	
	
	
	/**
	 * Return the distance of the target from the source node.
	 * @param target target node
	 * @return distance of the target from the source node
	 */
	public double getDistance(int target) {
		return this.distance[target];
	}
	
	/**
	 * Reconstruct the minimum path from the source to the target node
	 * in reverse order.
	 * @param target target node
	 */
	public void reconstructReversePath(int target) {
		int i = 0;
		this.reversePath.add(i, target);
		while(reversePath.get(i) > 0) {
			this.reversePath.add(i + 1, this.previous[this.reversePath.get(i)]);
			i++;
		}
	}
	
	/**
	 * Reconstruct the minimum path from the source to the target node.
	 * @param target target node
	 */
	public void reconstructPath(int target) {
		
		this.reconstructReversePath(target);

		for (int i = this.reversePath.size() - 1; i >= 0; --i) {
			this.path.add(this.reversePath.get(i));
		}
	}
	
	/**
	 * Calculate the path length from source to currentNode
	 * @param currentNode current node to which calculate the path length 
	 * @return path length
	 */
	public int pathLength(int currentNode) {
		int length = 0;
		int previousNode = this.previous[currentNode];
		
		while (previousNode > -1) {
			previousNode = this.previous[previousNode];
			length++;	
		}
		
		return length;
	}
	
	/**
	 * Calculate number of passenger at the current node, comparing 
	 * pathlength+1 and the capacity of the car.
	 * @param currentNode current node to which calculate the path length
	 * @return number of passenger at the current node
	 */
	public int passengerNumber(int currentNode) {
		if (this.carCapacity > this.pathLength(currentNode) + 1) {
			return this.pathLength(currentNode) + 1;
		}
		else {
			return this.carCapacity;
		}
	}
	
	/**
	 * Put the minimum path from the source to the target node in a string
	 * Use it with System.out.println();
	 * @return String that contains the minimum path
	 */
	public String pathToString() {
		String r = "";
		for (int i = 0; i < this.path.size(); i++) {
			if (i > 0) {
				r = r + " -> ";
			}
			r = r + this.path.get(i);
		}
		
		return r;
	}
	
}
